package LeetCode.exercise;

public class LCR170 {
    public static void main(String[] args) {
        LCR170 l = new LCR170();
        int[] arr = {9, 7, 5, 4, 6};
        int res = l.reversePairs(arr);
        System.out.println(res);
    }
    int[] tmp;

    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return mergeSort(record, 0, record.length - 1);
    }

    public int mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int res = 0;
        int mid = (start + end) / 2;
        res += mergeSort(nums, start, mid);
        res += mergeSort(nums, mid + 1, end);
        int left = start, right = mid + 1, i = 0;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                tmp[i++] = nums[left++];
            } else {
                res += mid - left + 1;
                tmp[i++] = nums[right++];
            }
        }
        while (left <= mid) {
            tmp[i++] = nums[left++];
        }
        while (right <= end) {
            tmp[i++] = nums[right++];
        }
        for (int j = start; j <= end; j++) {
            nums[j] = tmp[j - start];
        }
        return res;
    }
}
